package chapter26;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

/**
 * 最大流-推送重贴
 */
public class PushRelabel {

    public static void push(Graph G, EdgeNode u, EdgeNode v) {
        EdgeNode v1 = G.adjList.get(v.adj).firstEdge;
        int f = Math.min(u.e, v.f);
        v.f -= f;
        if (v.original) {

            EdgeNode u1 = v;
            while (u1.next != null && u1.next.key != u.key) {
                u1 = u1.next;
            }
            if (u1.key == v.key || u1.next == null) {
                EdgeNode v2 = new EdgeNode(u.key, u.adj);
                v2.original = false;
                if (v.f != v.c) {
                    v2.f = f;
                }
                insert(v, v2, v.c);
            } else {
                u1.next.f += f;
            }

        } else {
//            v.f += f;

            EdgeNode u1 = u;
            while (u1.next != null && u1.next.key != v.key) {
                u1 = u1.next;
            }
            if (u1.key == v.key || u1.next == null) {
                EdgeNode v2 = new EdgeNode(v.key, v.adj);
                v2.original = false;
                if (v.f != v.c) {
                    v2.f = f;
                }
                insert(u, v2, v.c);
            } else {
                u1.next.f -= f;
            }
        }
        u.e -= f;
        v1.e += f;
    }

    public static void relabel(Graph G, EdgeNode u) {
//        EdgeNode v = u;
//        int min = Integer.MAX_VALUE;
//        while (v != null) {
//            min = Math.min(min, v.h);
//            v = v.next;
//        }
//        if (min == 0) {
//            u.h++;
//        } else {
//            u.h += min;
//        }
        u.h++;
    }

    public static void initializePreFlow(Graph G, EdgeNode s) {
        EdgeNode s1 = G.adjList.get(s.adj).firstEdge;
        s1.h = G.numVertexes;
        EdgeNode v = s1.next;
        while (v != null) {
            EdgeNode v1 = G.adjList.get(v.adj).firstEdge;
            v.f = v.c;
            v1.e = v.c;
            s1.e -= v.c;

            EdgeNode s2 = new EdgeNode(s1.key, s1.adj);
            s2.f = v.c;
            insert(v1, s2, v.c);

            v = v.next;
        }

        for (VertexNode vertexNode : G.adjList) {
            EdgeNode u = vertexNode.firstEdge;
            EdgeNode v1 = u.next;
            while (v1 != null) {
                v1.f = v1.c;
                v1 = v1.next;
            }
        }
    }

    private static boolean check(Graph G) {
        for (VertexNode vertexNode : G.adjList) {
            if (vertexNode.firstEdge.e > 0) {
                return true;
            }
        }
        return false;
    }

    public static void genericPushRelabel(Graph G) {
        EdgeNode s = G.adjList.get(0).firstEdge;
        initializePreFlow(G, s);
        while (check(G)) {
            for (VertexNode vertex : G.adjList) {
                EdgeNode u = vertex.firstEdge;
                if (u.e > 0) {
                    EdgeNode v = u.next;
                    EdgeNode v1 = G.adjList.get(v.adj).firstEdge;
                    if (u.h <= v1.h) {
                        relabel(G, u);
                    } else if ((v.c - v.f > 0) && (u.h == v1.h + 1)) {
                        push(G, u, v);
                    }
                }
            }

        }
    }

    public static void discharge(Graph G, EdgeNode u) {
        while (u.e > 0) {
            EdgeNode v = u.current;
            EdgeNode v1 = u.next;
            while (v1 != null && v1.key != v.key) {
                v1 = v1.next;
            }
            v = v1;
            if (v == null) {
                relabel(G, u);
                u.current = u.N.getFirst();
            } else if (v.f > 0 && u.h == G.adjList.get(v.adj).firstEdge.h + 1) {
                push(G, u, v);
            } else {
                // TODO has bug
                int i = 0;
                while (i < u.N.size() && u.N.get(i).key != v.key) {
                    i++;
                }
                if (i + 1 == u.N.size()) {
                    u.current = null;
                } else {
                    u.current = u.N.get(i + 1);
                }
            }
        }
    }

    public static void relabelToFont(Graph G, EdgeNode s) {
        initializePreFlow(G, s);
        LinkedList<EdgeNode> L = new LinkedList<>();
        for (VertexNode vertexNode : G.adjList) {
            L.add(vertexNode.firstEdge);
        }
        for (EdgeNode u : L) {
            u.current = u.N.getFirst();
        }
        EdgeNode u = L.poll();
        while (u != null) {
            int oldHeight = u.h;
            discharge(G, u);
            if (u.h > oldHeight) {
                L.addFirst(u);
            }
            u = L.poll();
        }
    }

    public static void insert(EdgeNode x, EdgeNode y, int c) {
        EdgeNode pre = x;
        while (pre.next != null) {
            pre = pre.next;
        }
        y.firstEdge = x;
        y.c = c;
        pre.next = y;
    }

    public static class EdgeNode implements Cloneable {
        public char key;
        public EdgeNode firstEdge = this;
        public EdgeNode next;
        public int adj;
        public EdgeNode p;
        public EdgeNode current;
        public LinkedList<EdgeNode> N = new LinkedList<>();
        public int f;
        public int c;
        public int e;
        public int h;
        public boolean original = true;
        public boolean visited;

        public EdgeNode(char key, int adj) {
            this.key = key;
            this.adj = adj;
        }


        public EdgeNode(char key, int adj, int c, int f) {
            this.key = key;
            this.adj = adj;
            this.c = c;
            this.f = f;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            EdgeNode edgeNode = (EdgeNode) o;
            return Objects.equals(key, edgeNode.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }

        @Override
        public String toString() {
            return "EdgeNode{" +
                    "key=" + key +
                    ", f=" + f +
                    ", c=" + c +
                    ", e=" + e +
                    ", h=" + h +
                    ", o=" + original +
                    '}';
        }

        @Override
        protected Object clone() throws CloneNotSupportedException {
            return super.clone();
        }
    }

    public static class VertexNode implements Cloneable {
        public String key;
        public EdgeNode firstEdge;

        public VertexNode(EdgeNode firstEdge) {
            this.firstEdge = firstEdge;
        }

        @Override
        public String toString() {
            return "VertexNode{" +
                    "key='" + key + '\'' +
                    ", firstEdge=" + firstEdge +
                    '}';
        }

        @Override
        protected Object clone() throws CloneNotSupportedException {
            return super.clone();
        }
    }

    public static class Graph implements Cloneable {
        public List<VertexNode> adjList = new ArrayList<>();
        public int numVertexes;
        public int numEdges;

        @Override
        public String toString() {
            return "Graph{" +
                    "adjList=" + adjList +
                    ", numVertexes=" + numVertexes +
                    ", numEdges=" + numEdges +
                    '}';
        }

        @Override
        protected Object clone() throws CloneNotSupportedException {
            return super.clone();
        }
    }

}
